package com.learn.acm.bytedance;

import com.google.gson.Gson;
import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author zhongshitao
 * @date 2020/9/24 2:58 下午
 */
public class Solution496 {


    @Test
    public void test496() {
        System.out.println(new Gson().toJson(nextGreaterElement(new int[]{4,1,2},new int[]{1,3,4,2})));
    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer,Integer> map = new HashMap();
        int[] res = new int[nums1.length];
        Stack<Integer> stack = new Stack();
        for(int i : nums2) {
            while(!stack.empty() && i > stack.peek()) {
                map.put(stack.pop(),i);
            }
            stack.push(i);
        }
        while(!stack.empty()) {
            map.put(stack.pop(), -1);
        }
        for(int i =0;i<nums1.length;i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
